/**
 * 题目描述：https://leetcode.cn/problems/remove-element/description/
 */

// 方法一：双指针
// 时间复杂度：O(n)
// 空间复杂度：O(1)
const removeElement = function(nums, val) {
    const len = nums.length; // 数组长度
    let left = 0; // 左指针指向下一个将要赋值的位置
    for (let right = 0; right < len; right++) { // 右指针指向当前将要处理的元素，right总是会向后移动的
        if (nums[right] !== val) { // 如果right指针指向的当前元素不等于val,则将其赋值到left指针指向的位置
            nums[left] = nums[right];
            left++; // left指针指向下一个将要赋值的位置
        }
        // 如果相等，说明left指向的元素等于val，要进行覆盖，left不动，找下一个不等于val的元素
    }
    return left; // left的值就是数组中不等于val的元素的个数
};

// 方法二：双指针优化，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列，此方法避免了需要保留的元素的重复赋值操作
// 时间复杂度：O(n)
// 空间复杂度：O(1)
const removeElement2 = function(nums, val) {
    // right初始值为nums.length，则循环条件 left < right，nums[right - 1]
    // right初始值为nums.length - 1，则循环条件 left <= right, nums[right]
    let left = 0, right = nums.length - 1; // 左右指针，left指针初始时指向数组的第一个元素，right指针初始时指向数组的最后一个元素，
    while (left <= right) { // 当左指针小于右指针时
        if (nums[left] === val) { // 如果左指针指向的元素等于val
            nums[left] = nums[right]; // 将右指针指向的元素赋值到左指针指向的位置
            right--; // 右指针向前移动
        } else {
            left++; // 左指针向后移动
        }
    }
    return left; // 返回左指针的值，就是数组中不等于val的元素的个数
}
